import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class project {
    List<Integer> list=new ArrayList<>();
    public TreeNode balanceBST(TreeNode root) {
        gets(root);
        return build(0,list.size()-1);
    }
    public void gets(TreeNode root){
        if(root.left!=null){
            gets(root.left);
        }
        list.add(root.val);
        if(root.right!=null){
            gets(root.right);
        }
    }
    public TreeNode build(int l,int r){
        int mid=(l+r)/2;
        TreeNode root=new TreeNode(list.get(mid));
        if(l<=mid-1){
            root.left=build(l,mid-1);
        }
        if(mid+1<=r){
            root.right=build(mid+1,r);
        }
        return root;
    }


















    public int goodNodes(TreeNode root) {
        return dfs(root,root.val);
    }
    public int dfs(TreeNode root,int value){
        if(root==null){
            return 0;
        }
        int sum=0;
        if(root.val>=value){
            sum++;
            value=root.val;
        }
        return dfs(root.left, value)+dfs(root.right,value)+sum;
    }
















    public int countElements(int[] nums) {
        Arrays.sort(nums);
        int max=nums[nums.length-1];
        int min=nums[0];
        int count=0;
        for(int i=1;i<nums.length-1;i++){
            int tmp=nums[i];
            if(tmp!=min&&tmp!=max){
                count++;
            }
        }
        return count;
    }
























    public String[] divideString(String s, int k, char fill) {
        int len=s.length();
        List<String> list=new LinkedList<>();
        for(int i=0;i<=len-k;i+=k){
            list.add(s.substring(i,i+k));
        }
        if (len % k != 0) {
            StringBuilder sb = new StringBuilder();
            sb.append(s.substring(len - len % k, len));
            for (int i = len % k; i < k; i++) {
                sb.append(fill);
            }
            list.add(sb.toString());
        }
        return list.toArray(new String[0]);
    }


















    public int minimumCost(int[] cost) {
        int sum=0;
        int len=cost.length;
        Arrays.sort(cost);
        int index=len-1;
        int count=0;
        while (index>=0){
            sum+=cost[index];
            count++;
            if(count>2){
                sum-=cost[index];
                count=0;
            }
            index--;
        }
        return sum;
    }
}
